/*
 * @lc app=leetcode.cn id=138 lang=golang
 *
 * [138] 随机链表的复制
 */

// @lc code=start
/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Next *Node
 *     Random *Node
 * }
 */

func copyRandomList(head *Node) *Node {
	cache := map[*Node]*Node{}

	ptr := head
	list := &Node{}
	t := list
	for ptr != nil {
		temp := &Node{Val: ptr.Val, Next: nil, Random: ptr.Random}
		cache[ptr] = temp

		ptr = ptr.Next
		t.Next = temp
		t = t.Next
	}
	t = list.Next
	for t != nil {
		random := t.Random
		t.Random = cache[random]
		t = t.Next
	}
	return list.Next
}

// @lc code=end

